Among the many data processing methods that are used with data streams is "pattern matching". This process "relates" or matches acquired data to a predetermined pattern or template. Some matching techniques use mathematical or geometrical measurements of the data pattern and the template to yield numerical values of the degree of matching. These matching techniques are sometimes referred to as "correlation methods" for matching. These correlation methods employ theorems of Statistics Theory.
Examples of correlation and the use of correlation are found in such divergent fields as medical imaging for diagnostic purposes and military surveillance imaging for the purpose of locating enemy units, communications (especially for error detection and correction, and for the detection of specific signals), etc.
Correlation methods and systems are also used, for example, to determine the location of R-waves in an Electro-Cardiogram (ECG or EKG) trace and to classify the heart beat (according to the shape of the so-called QRS shape of the ECG trace) into one of several types.
A popular and widely studied correlation technique in use is known as "linear correlation". This is a statistical technique wherein correlation is determined by the value of the criteria R; where: ##EQU1## where Y is the template data, X is the acquired data, Y is the arithmetic mean of the template and X is the arithmetic mean of the acquired data; RE[1,-1]--that is R has a value between +1 and -1 inclusive. It has a value of +1 if the acquired shape and the template shape look alike, and -1 if one is an upside down exact match of the other; in these cases one can write for all i: EQU Yi=aXi+b (a linear relationship)
and R equals:
+1 if a is larger than 0,
-1 if a is smaller than 0;
The symbols Xi and Yi denote ordered sets, with i the ordinal index; R has a value of 0 if there is no relationship between the acquired pattern and the template pattern; and VAR is the statistical variation.
A match is usually declared if R or .vertline.R.vertline. (its absolute or unsigned value) has a value above a predetermined threshold value. This threshold is usually set close enough to 1 (say, 0.85) to avoid spurious matchings, especially if the data is "noisy".
The data being examined is usually a representation of some physical information in the object examined. Due to system limitations and inaccuracies, the same physical information will not necessarily be represented by the same data value if measured repeatedly. These differences are referred to as "noise". The larger the spread of the data values for a given physical information, the noisier the data stream of the measuring system is considered to be. Such "noise" may create a spurious pattern, remindful of the "template" pattern, it is usually the aim of the correlation (or any matching) method to avoid those spurious patterns.
The linear correlation declares a match according to linear dependency only. The scales can be vastly different between the template and data, and yet R will equal 1. While this is what is needed for some applications, many applications look for a correlation method that recognizes scale as well as shape.
Another problem with this prior art technique is that it requires relatively large amounts of computer time and memory. This is caused by several things; such as:
a. Averages of acquired data are required to provide a fiducial or reference value; which means, it is necessary to calculate averages before computing the correlation value. It also means that all the data values have to be retained in the computer if a correlation factor is calculated for consecutive points. The same is true if for a given point the correlation factor is calculated over a number of data set sizes. In both cases, new means have to be calculated for each change. PA0 b. For each value of i at least two multiplications are required, multiplication being a relatively time consuming computer operation. PA0 c. Square roots are also required which take up more computer time. PA0 A. There are no multiplications involved; PA0 B. There are no square roots involved; PA0 C. The number of data points processed is smaller by 1, as i=1 can be eliminated from all summations; PA0 D. Changing the size of the data set involves no new calculations on the template or the value of X1 (which replaced the mean X which had to be recalculated); and PA0 E. X1 is easily found when changing the data set, compared to a recalculation of X. PA0 a. If the ordered set Xi differs by a constant from Yi but has the same scale, then r=1. PA0 b. For any set of Xi and any set of Yi, r is between +1 and -1, inclusive. PA0 c. If there is a linear relationship Xi=aYi+b PA0 d. For .vertline.a.vertline..fwdarw..infin., r.fwdarw.-1 (i.e. the larger the absolute value of a, the closer r is to -1). PA0 a. It is sensitive to scale. PA0 b. It is more sensitive to changes (a lower threshold is needed). PA0 c. The set Xi.dbd.C has a linear correlation R.dbd.O with any different set Yi, but r=-1. PA0 d. A set Xi which relates to Yi in such a way as to evenly cover a circular or annular area in the Z-Y plane has a linear correlation R.dbd.O regardless of the values of Xi and Yi; such sets do not have a definite psuedo-correlation, although r is usually negative. PA0 e. When Yi is a linear set: Yi=Ai+B, and Xi is another linear set: Xi=Ci+D, then the linear correlation R equals 1, while the pseudo-correlation r equals 1-2*.vertline.C-A.vertline./(.vertline.C.vertline.+.vertline.A.vertline.); thus if C and A have different signs r=-1. PA0 (a) Multi-template pseudo-correlation. --The speed of the method enables comparing the incoming data stream with several templates to decide which template fits which part of the data stream. PA0 (b) Multi-data pseudo-correlation. --The speed of the method enables parallel comparisons of a template with several data streams. PA0 (c) Multi-dimensional pseudo-correlation or Vector pseudo-correlation. --Assume that the template Y and the acquired data X both are n-dimensional vectors: EQU X=(.sup.1 x, .sup.2 x, .sup.3 x, . . . , .sup.n x) EQU Y=(.sup.1 y, .sup.2 y, .sup.3 y, . . . , .sup.n y) (5)
Accordingly, with the prior art methods, excessive time is required for the computations, making the use of these prior art correlation methods limited for real-time application.
Scientists in the data processing fields, for example where data processing is done for pattern matching purposes, are always searching for new methods and systems which will decrease the time required for the correlation computations and improve the accuracy of the final results. Accordingly, an object of the present invention is to provide new, faster and improved correlation methods and systems. Herein the new correlation methods are referred to as pseudo correlation since they do not follow the classical prior art correlation methods or systems. A pertinent article on correlation authored by D. I. Barnea and H. F. Silverman appears in Transactions on Computers, 1972.